class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {

            int len = nums.size();
            vector<vector<int>> v;
            if (len < 3) {
                return v;
            } else if (len == 3) {
                if (nums[0] + nums[1] + nums[2] == 0) {
                    v.push_back(nums);
                }
                return v;
            }

            int SUM = 0;
            int i, j, k;
            int val, tmp;
            set<int> outer;
            for (i=0; i<len-2; i++) {
                if (outer.find(nums[i]) != outer.end())
                    continue;
                outer.insert(nums[i]);
                val = SUM - nums[i];
                vector<vector<int>> inner = twoSum(nums, i+1, val);
                for (auto s : inner) {
                    v.push_back(get(nums[i], s[0],s[1]));
                }
            }
            return v;
        }

        vector<vector<int>> twoSum(vector<int>& nums, int idx, int sum) {
            vector<vector<int>> v;
            int len = nums.size();
            if (len-idx < 2) {
                return v;
            }

            if (len-idx == 2) {
                if(nums[0] + nums[1] == sum) {
                    v.push_back(get(nums[0], nums[1]));
                }
                return v;
            }

            int i, j, k;
            int val, tmp;
            set<int> outer;
            for (i=idx; i<len-1; i++) {
                if (outer.find(nums[i]) != outer.end())
                    continue;
                outer.insert(nums[i]);

                set<int> inner;
                for (j=i+1; j<len; j++) {
                    if (nums[j] + nums[i] == sum) {
                        if (inner.find(nums[j]) == inner.end()) {
                            v.push_back(get(nums[i], nums[j]));
                        }
                        inner.insert(nums[j]);
                    }
                }
            }
            return v;
        }
        vector<int> get(int a, int b, int c) {
            vector<int> r = {a,b,c};
            return r;
        }
        vector<int> get(int a, int b) {
            vector<int> r = {a,b};
            return r;
        }

};


